package primary.code01_Sort;

/**
 * 一个数出现奇数次
 * 两个数出现奇数次
 * <p>
 * 利用int类型的异或运算的特点：
 * 与自身异或为0
 * 与0异或不变
 * 与1异或取反
 */
public class Code03_OddTimes {
    /*一个数出现奇数次*/
    public static void oddTimes1(int[] arr) {
        int eor = 0;
        for (int i : arr) {
            eor ^= i;
        }
        System.out.println(eor);
    }

    /*两个数出现奇数次*/
    public static void oddTimes2(int[] arr) {
        int eor = 0;
        for (int i : arr) {
            eor ^= i;
        }
        //1000100
        //0111011
        //0111100
        int rightOne = eor & (~eor + 1);//找到最右边的1

        int eor$ = 0;
        for (int i : arr) {
            if ((i & rightOne) != 0) eor$ ^= i;
        }
        System.out.println(eor$ + "  " + (eor ^ eor$));
    }

    public static void oddTimes2Test(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        int copy = eor;
        int latestOne = eor & (~eor + 1);
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & latestOne) != 0) {
                eor ^= arr[i];
            }
        }
        System.out.println(eor + "  " + (eor ^ copy));

    }

    public static void main(String[] args) {
        int[] arr1 = {34, 7, 4, 7, 4, 23, 48, 48, 23, 23, 23};
        oddTimes1(arr1);

        int[] arr2 = {34, 7, 4, 7, 4, 23, 48, 48, 11, 23, 23, 23};
        oddTimes2(arr2);
        oddTimes2Test(arr2);
    }
}
